package sort;

/**
 * @description:
 * @author: w_jingbo
 * @date: 2023/9/18
 * @Copyright: 博客：http://coisini.wang
 */
public class Partition {

    public static void main(String[] args) {
        int[] arr = new int[] {3 , 1, 4 , 2, 2 ,1 ,3} ;
        partition2(arr,0,arr.length-1,2);
        for (int i : arr) {
            System.out.println(i);
        }
    }

    /**
     * 将一个数组根据num分出三部分，<num的在数组左侧，==num的在中间，>num的在数组右侧，可以无序。要求时间复杂度O（N）
     * @param arr
     * @param L
     * @param R
     * @param num
     * @return
     */
    public static int partition1(int[] arr,int L ,int R,int num){
        int less = L - 1 ;
        int more = R + 1 ;
        int index = L ;
        while(index < more){
            if(arr[index] < num){
                swap(arr,index++,++less);
            }else if(arr[index] == num){
                index++;
            }else {
                swap(arr,index,--more);
            }
        }
        return 0;
    }

    public static int partition2(int[] arr,int L ,int R,int num){

        int less = L - 1 ;
        int index = L ;
        while(index <= R){
            if(arr[index] <= num){
                swap(arr,index++,++less);
            }else {
                index++;
            }
        }
        return 0 ;

    }

    public static void swap(int[] arr, int i, int j) {
        int tmp = arr[i];
        arr[i] = arr[j];
        arr[j] = tmp;
    }

}
